package com.bing.java.other;

/**
 * 
 * @author bing
 *
 *         2019年11月21日 上午9:42:24
 * 
 *         输入一个数字n 如果n为偶数则除以2，若为奇数则加1或者减1，直到n为1，求最少次数 写出一个函数
 * 
 */
public class PinDuoDuo2 {

	public static void main(String[] args) {
		int n = 13;
		int num = getNum(n);
		System.out.println(num);
	}

	public static int getNum(int n) {
		if (n <= 1) {
			return 0;
		}
		int[] res = new int[n + 1];
		res[0] = 0;
		res[1] = 0;
		for (int i = 2; i <= n; i++) {
			if ((i & 1) == 0) {
				res[i] = res[i / 2] + 1;
			} else {
				res[i] = Math.min(res[(i + 1) / 2], res[(i - 1) / 2]) + 2;
			}
		}
		return res[n];
	}

	public static int getNum2(long n) {
		if (n <= 1) {
			return 0;
		}

		if ((n & 1) == 0) {
			return getNum2(n / 2) + 1;
		} else {
			long a = (n - 1) / 2;
			long b = (n + 1) / 2;

			return Math.min(getNum2(a), getNum2(b)) + 2;
		}
	}
}
